package org.czl.leetcode4;

public class l375 {


    int[][] dp;
    public int getMoneyAmount(int n) {
        dp = new int[n + 1][n + 1];
        for(int i = 0; i < n + 1; i++){
            for(int j = 0; j < n + 1; j++){
                dp[i][j] = -1;
            }
        }
        return f(1, n);
    }
    //表示left 到right至少要多少钱
    int f(int left, int right){
        if(left >= right){
            return 0; // 因为区间只有一个数的话不用猜 必中
        }
        if(right == left + 1){
            return left;
        }
        if(dp[left][right] != -1)return dp[left][right];
        int ans = 0x3f3f3f3f;
        for(int i = left; i <= right; i++){
            int ret1 = f(left, i - 1) + i;//左区间要这么多钱才能猜完
            int ret2 = f(i + 1, right) + i;//右区间要猜完需要的钱数
            ans = Math.min(ans, Math.max(ret2, ret1));
        }
        dp[left][right] = ans;
        return ans;
    }
}
